package codingforgreat.class48;

/***
 * 题目描述:
 * 由空地和墙组成的迷宫中有一个球。球可以向上（u）下（d）左（l）右（r）四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。迷宫中还有一个洞，当球运动经过洞时，就会掉进洞里。
 *
 * 给定球的起始位置，目的地和迷宫，找出让球以最短距离掉进洞里的路径。 距离的定义是球从起始位置（不包括）到目的地（包括）经过的空地个数。通过'u', 'd', 'l' 和 'r'输出球的移动方向。 由于可能有多条最短路径， 请输出字典序最小的路径。如果球无法进入洞，输出"impossible"。
 *
 * 迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。
 *
 * 示例:
 * 示例1:
 *
 * 输入 1: 迷宫由以下二维数组表示
 *
 * 0 0 0 0 0
 * 1 1 0 0 1
 * 0 0 0 0 0
 * 0 1 0 0 1
 * 0 1 0 0 0
 *
 * 输入 2: 球的初始位置 (rowBall, colBall) = (4, 3)
 * 输入 3: 洞的位置 (rowHole, colHole) = (0, 1)
 *
 * 输出: "lul"
 *
 * 解析: 有两条让球进洞的最短路径。
 * 第一条路径是 左 -> 上 -> 左, 记为 "lul".
 * 第二条路径是 上 -> 左, 记为 'ul'.
 * 两条路径都具有最短距离6, 但'l' < 'u'，故第一条路径字典序更小。因此输出"lul"。
 */
public class Problem_0499_TheMazeIII {
    public static class Node{
        public int r;
        public int c;//位置（r，c）
        public int d;//方向 0123 -> 上下左右 4 ： 起始
        public String path;//路径
        public Node(int r, int c, int d, String path){
            this.r = r;
            this.c = c;
            this.d = d;
            this.path = path;
        }
    }
    public static int[][] to = { { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, 0 }, { 0, 0 } };//方位数组
    public static String[] re = { "d", "l", "r", "u" };
    public static String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        int n =  maze.length;
        int m =  maze[0].length;
        Node[] q1 = new Node[n * m],q2 = new Node[n*m];
        int s1 = 0;
        int s2 = 0;
        boolean[][][] visited = new boolean[n][m][4];
        s1 = spread(maze,n,m,new Node(ball[0],ball[1],4,""),visited,q1,s1);
        while(s1 != 0){
            for(int i = 0;i < s1;i++){
                //收集 遍历
                Node cur = q1[i];
                if (hole[0] == cur.r && hole[1] == cur.c) {
                    return cur.path;
                }
                s2 = spread(maze, n, m, cur, visited, q2, s2);
            }
            Node[] tmp = q1;
            q1 = q2;
            q2 = tmp;
            s1 = s2;
            s2 = 0;
        }
       return null;
    }
    public static int spread(int[][] maze,int n,int m,Node cur,boolean[][][] v,Node[] q,int size){
        int d = cur.d;
        int r = cur.r + to[d][0];
        int c = cur.c + to[d][1];
        //分裂
        if((d == 4) || r < 0 || r >= n || c < 0 || c >= m || maze[r][c] != 0){
            for(int i = 0;i < 4;i++){
                if(i !=d){
                    r = cur.r + to[i][0];
                    c = cur.c + to[i][1];
                    if (r >= 0 && r < n && c >= 0 && c < m && maze[r][c] == 0 && !v[r][c][i]) {
                        v[r][c][i] = true;
                        Node next = new Node(r, c, i, cur.path + re[i]);
                        q[size++] = next;
                    }
                }
            }

        }else {//不分裂
            if (!v[r][c][d]) {
                v[r][c][d] = true;
                q[size++] = new Node(r, c, d, cur.path);
            }
        }
        return size;
    }

}
